package com.zombies.list.linkedlist.singlelinkedlist;

import com.zombies.list.adt.MyList;


/**
 * 线性表的链式存储结构实现(单链表)
 *
 * @author zombies
 * @create 2022-04-11 9:58
 */
public class MySingleLinkedList<E> implements MyList<E> {

    private Node<E> head;

    /*
    注释了这个变量，由成员变量改成局部变量
     private Node<E> temp;
     */


    public MySingleLinkedList() {
        //约定head引用指向一个空节点
        head = new Node<E>(null,null);
    }

    private static class Node<E>{
        E data;
        Node<E> next;

        /**
         * 使用泛型的时候 构造器中的泛型怎么写?
         * 一开始我在构造方法方法后面带着泛型结果报错了，下面就是正确的写法
         *
         * @param node
         * @param data
         */

        public Node(Node<E> node,E data){
            this.next = node;
            this.data = data;
        }

    }


    /**
     * 查看线性表是否为空
     *
     * @return 为空返回true 反之false
     */
    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    /**
     * 查看线性表是否已满
     * 单链表没有溢出这一说法
     * @return 满了返回true 反之false
     */
    @Override
    public boolean isFull() {
        return false;
    }

    /**
     * 返回线性表的第一个元素
     *
     * @return 返回第一个元素
     */
    @Override
    public E getFirst() {
        Node<E> temp = head;
        if(temp.next == null){
            return  null;
        }else {
            return temp.next.data;
        }
    }

    /**
     * 返回线性表的最后一个元素
     *
     * @return 返回最后一个的元素
     */
    @Override
    public E getLast() {
        Node<E> temp = head;
        if(temp.next == null){
            return null;
        }
        //需要这个while循环结束后出来的temp是指向最后一个节点
        while (temp.next != null){
            temp =temp.next;
        }

        return temp.data;
    }

    /**
     * 删除线性表的第一个元素，并将该值返回
     *
     * @return 返回删除的第一个元素
     */
    @Override
    public E removeFirst() {
        Node<E> temp = head;
        E e = null;
        if(temp.next == null){
            return null;
        }else {
            //定义个临时变量接受元素
            e = temp.next.data;
            head.next = head.next.next;
            return  e;
        }
    }

    /**
     * 删除线性表的最后一个元素，并将该值返回
     *
     * @return 返回删除的最后一个元素
     */
    @Override
    public E removeLast() {
        //获取头节点
        Node<E> temp = head;
        E e = null;
        if(temp.next == null){
            return null;
        }else {
            while (temp != null){
                if(temp.next.next == null){
                    e = temp.next.data;
                    temp.next = null;
                    /*
                        return e;//疑问???：这个return e;移到while循环外面就不行了
                        解决了,局部变量没有赋值直接通过return返回导致的
                     */

                }
                temp = temp.next;
            }
            return e; //要是局部变量没有赋值就直接通过return返回,会报异常
        }
    }

    /**
     * 将元素插入到线性表的开头位置
     *
     * @param e 将要插入开头的元素
     */
    @Override
    public void addFirst(E e) {
        //获取头节点
        Node<E> temp = head;
        Node<E> node = new Node<>(null,e);
        if(temp.next == null){
            temp.next = node;
        }else {
            //先用新节点指向头节点后一个节点,再用头节点指向新节点
            node.next = temp.next;
            temp.next = node;
        }


    }

    /**
     * 将元素插入到线性表的末尾位置
     *
     * @param e 将要插入末尾的元素
     */
    @Override
    public void addLast(E e) {
        Node<E> temp = head;
        Node<E> node = new Node<>(null, e);
        while (temp.next != null){
            temp = temp.next;
        }

        temp.next = node;

    }

    /**
     * 检查元素是否在线性表中
     *
     * @param e 将要检索的目标元素
     * @return 存在返回true，反之返回false
     */
    @Override
    public boolean contains(E e) {
        Node<E> temp = head;

        while (e != null && temp != null && !e.equals(temp.data) ){
            temp = temp.next;
        }

        if(temp == null){
            return false;
        }else {
            return true;
        }
    }

    /**
     * 返回线性表元素的个数
     *
     * @return 返回线性表元素的个数
     */
    @Override
    public int size() {
        Node<E> temp = head;
        int len = 0;
        while (temp != null){
            temp = temp.next;
            len++;
        }
        return len - 1; //减去head节点
    }

    /**
     * 将元素插入到线性表的末尾
     *
     * @param e 将要插入的目标元素
     * @return 成功则返回true，失败则返回false
     */
    @Override
    public boolean add(E e) {
        Node<E> node = new Node<>(null,e);
        Node<E> temp = head;

        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = node;

        return true;
    }

    /**
     * 将第一次出现的元素删除
     *
     * @param e 将要删除的目标元素
     * @return 成功则返回true，失败则返回false
     */
    @Override
    public boolean remove(E e) {
        Node<E> temp = head;

        if(temp.next == null){
            return false;
        }

        while (temp.next != null){
            if(e != null && e.equals(temp.next.data)){
                if(temp.next.next == null){
                    temp.next = null;
                }else {
                    temp.next = temp.next.next;
                }
                return true;
            }
            temp = temp.next;
        }

        return false;
    }

    /**
     * 将list中的元素全部添加到线性表末尾
     *
     * @param list 将要添加的目标元素集合
     * @return 成功则返回true，失败则返回false
     */
    @Override
    public boolean addAll(MyList<E> list) {
        return false;
    }

    /**
     * 将list中的元素全部添加到线性表的指定索引位置，位置之后的元素后移
     *
     * @param index 线性表的index位置
     * @param list  将要添加的目标元素集合
     * @return 成功则返回true，失败则返回false
     */
    @Override
    public boolean addAll(int index, MyList<E> list) {
        return false;
    }

    /**
     * 删除线性表中的所有元素
     */
    @Override
    public void clear() {
        head.next = null;
    }

    /**
     * 返回线性表的index位置的元素
     *
     * 注意：head节点作为第0个位置，所以这个index就是从1开始计算的
     *
     * @param index 线性表的index位置
     * @return 返回index位置所在元素
     */
    @Override
    public E get(int index) {
        if(index <= 0 || index > size()){
            throw new IllegalArgumentException("index 超过范围了");
        }

        //获取头节点
        Node<E> temp = head;

        //考虑情况 1、要是index大于链表实际个数报错 不然返回对应的节点data
        int j = 0;

        while (j != index && temp!= null){  //满足条件搜索到表尾或者满足条件index

            temp = temp.next;
            j++;
        }

        if(temp == null){
            return  null;

        }else {
            return temp.data;
        }

    }

    /**
     * 以元素e替代线性表index位置的元素，并返回被取代的元素
     * 约定链表的位置从1开始，0表示head节点
     *
     * @param index 线性表的index位置
     * @param e     将要插入到index位置的元素
     * @return 返回index位置所在元素
     */
    @Override
    public E set(int index, E e) {
        if (index <= 0 || index > size()) {
            throw new IllegalArgumentException("index 不符合规范");
        }
        Node<E> temp = head;
        Node<E> node = new Node<E>(null,e);
        int j = 0;
        E eTemp = null;

        //得到的temp是替换元素的前一个位置
        while (j != index - 1 && temp != null){
            temp = temp.next;
            j++;
        }

        if(temp.next == null){
            temp.next = node;
            return null;
        }else{
            if(temp.next.next == null){
                eTemp = temp.next.data;
                temp.next = node;
                return eTemp;
            }else {
                eTemp = temp.next.data;
                node.next = temp.next.next;
                temp.next = node;
                return eTemp;
            }
        }
    }

    /**
     * 将元素e插入到线性表index位置，其他元素后移
     *
     * @param index 线性表的index位置
     * @param e     将要插入到index位置的元素
     */
    @Override
    public void add(int index, E e) {
        if (index <= 0 || index > size()) {
            throw new IllegalArgumentException("index 不符合规范");
        }
        Node<E> temp = head;
        Node<E> node = new Node<E>(null,e);
        int j = 0;
        //得到的temp是插入元素位置的前一个位置
        while (j != index - 1 && temp != null){
            temp = temp.next;
            j++;
        }
        if(temp.next == null){
            temp.next = node;
        }else {
            node.next = temp.next;
            temp.next = node;
        }

    }

    /**
     * 删除线性表中index位置的元素，并返回
     *
     * @param index 线性表的index位置
     * @return 返回指定位置被删除的元素
     */
    @Override
    public E remove(int index) {
        if (index <= 0 || index > size()) {
            throw new IllegalArgumentException("index 不符合规范");
        }
        Node<E> temp = head;
        int j = 0;
        E e = null;
        //得到的temp是插入元素位置的前一个位置
        while (j != index - 1 && temp != null){
            temp = temp.next;
            j++;
        }
        if(temp.next.next == null){
            e = temp.next.data;
            temp.next = null;
            return e;
        }else {
            e = temp.next.data;
            temp.next = temp.next.next;
            return e;
        }

    }

    /**
     * 返回元素e在线性表中第一次出现的位置，若不存在就返回-1
     *
     * @param e 查询的目标元素
     * @return 若存在返回index，反之返回-1
     */
    @Override
    public int indexOf(E e) {
        Node<E> temp = head;
        int l = 1;

        while (temp.next != null){
            if(temp.next.data.equals(e)){
                return l;
            }
            temp = temp.next;
            l++;
        }
        return -1;
    }

    /**
     * 返回元素e在线性表中最后一次出现的位置，若不存在就返回-1
     *
     * @param e 查询的目标元素
     * @return 若存在返回index，反之返回-1
     */
    @Override
    public int lastIndexOf(E e) {
        Node<E> temp = head;
        int l = 1;
        int index = -1;

        while (temp.next != null){
            if(temp.next.data.equals(e)){
                index = l;
            }
            temp = temp.next;
            l++;
        }
        return index;
    }

    /**
     * 返回被反转的线性表
     *
     * @return 返回一个被反转的线性表
     */
    @Override
    public MyList<E> getReverseList() {
        Node<E> temp = head.next;
        Node<E> nHead = new Node<>(null,null);
        Node<E> t;

        while (temp != null){
            t = temp;
            temp = temp.next;
            t.next = nHead.next;
            nHead.next = t;
        }

        this.head = nHead;
        return this;
    }


    /**
     * 就是一个展示线性表所有的数据
     */
    @Override
    public void show() {
        Node<E> temp = head;
        while (temp != null){
            System.out.printf("-"+ temp.data + "-");
            temp = temp.next;
        }
        System.out.println();
    }
}
